package seqlist.leetcode;

/**
 * LeetCode第203号问题- 删除链表中所有值为val节点
 */
public class Num203 {
    public static void main(String[] args) {
        // 1.创建一个相同的链表
        // [1,2,6,3,4,5,6]
        ListNode head = build();
        Num203 num203 = new Num203();
        ListNode newHead = num203.removeElements(head,6);
        System.out.println(newHead);
    }
    // 创建一个链表
    public static ListNode build() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(6);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(5);
        ListNode node7 = new ListNode(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        return node1;
    }
    // 虚拟头节点法
//    public ListNode removeElements(ListNode head, int val) {
//        ListNode dummyHead = new ListNode(-1);
//        // 连接原来的链表
//        dummyHead.next = head;
//        ListNode prev = dummyHead;
//        while (prev.next != null) {
//            if (prev.next.val == val) {
//                prev.next = prev.next.next;
//            }else {
//                // prev下一个不是待删除节点，prev继续向后移动一个位置
//                prev = prev.next;
//            }
//        }
//        return dummyHead.next;
//    }


    // 删除当前链表中所有值为val的节点,返回删除后链表的头节点
//    public ListNode removeElements(ListNode head, int val) {
//        // 头节点就是待删除的节点
//        while (head != null && head.val == val) {
//            head = head.next;
//        }
//        if (head == null) {
//            return null;
//        }else {
//            // 此时头节点一定不是待删除节点且链表不为空
//            ListNode prev = head;
//            while (prev.next != null) {
//                if (prev.next.val == val) {
//                    ListNode cur = prev.next;
//                    prev.next = cur.next;
//                } else {
//                    // 只有当prev.next.val != val
//                    prev = prev.next;
//                }
//            }
//        }
//        return head;
//    }
    // 注意语义!
    // 给定一个头节点为head的链表，
    // 就可以删除该链表中所有值为val节点并返回删除后的头节点
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        // 将head.next以及之后节点交给removeElements解决
        // head.next更新为删除后的子链表的头节点
        head.next = removeElements(head.next,val);
        if (head.val == val) {
            return head.next;
        }
        return head;
    }
}
